package zhengqc.list;

public class ArrayList<E> extends AbstractList<E> {
    /* 动态数组的元素数据 */
    private E[] elementData;
    /* 动态数组默认容量大小 */
    private static final int DEFAULT_CAPACITY = 5;

    /* 动态调整数组容量 */
    private void adjustCapacity(int newCapacity) {
        E[] newElementData = (E[])(new Object[newCapacity]);
        for (int i = 0; i < size; ++i) {
            newElementData[i] = elementData[i];
        }
        elementData = newElementData;
    }
    /* 获取动态数组的元素容量 */
    public int getCapacity() {
        return elementData.length;
    }

    /* 构造函数 */
    public ArrayList(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        this.elementData = (E[]) (new Object[capacity]);
        this.size = 0;
    }
    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }
    public ArrayList(E[] array) {
        this.elementData = (E[]) (new Object[array.length]);
        this.size = array.length;
        for (int i = 0; i < this.size; ++i) {
            this.elementData[i] = array[i];
        }
    }

    public void swap(int i, int j) {
        if (i < 0 || i >= this.size ||
            j < 0 || j >= this.size) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        E temp = elementData[i];
        elementData[i] = elementData[j];
        elementData[j] = temp;
    }

    @Override /* 获取动态数组指定元素的位置 */
    public int indexOf(E element) {
        for (int i = 0; i < size; ++i) {
            if (elementData[i].equals(element)) {
                return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    @Override /* 清空动态数组的所有元素 */
    public void clear() {
        this.size = 0;
        this.adjustCapacity(DEFAULT_CAPACITY);
    }

    @Override /* 在动态数组的 index 位置添加元素 element*/
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        // 将数组容量扩充为原来的 2 倍
        if (this.size == elementData.length) {
            adjustCapacity(elementData.length << 1);
        }
        for (int i = this.size-1; i >= index; --i) {
            elementData[i+1] = elementData[i];
        }
        elementData[index] = element;
        ++size;
    }
    @Override /* 在动态数组开始位置添加元素 element*/
    public void addFirst(E element) {
        add(0, element);
    }

    @Override /* 在动态数组末尾位置添加元素 element*/
    public void addLast(E element) {
        add(this.size, element);
    }

    @Override /* 删除动态数组的 index 位置的元素 */
    public E remove(int index) {
        rangeCheck(index);
        E oldElement = elementData[index];
        for (int i = index+1; i < this.size; ++i) {
            elementData[i-1] = elementData[i];
        }
        --this.size;
        // 在保证动态数组缩容后的容量比默认容量大的情况下, 当动态数组的容量为数组元素的4倍以上, 则将动态数组的容量减半
        if (size <= (elementData.length >> 2) && (elementData.length >> 1) >= DEFAULT_CAPACITY) {
            adjustCapacity (elementData.length >> 1);
        }
        return oldElement;
    }

    @Override /* 删除动态数组开始位置的元素 */
    public E removeFirst() {
        return remove(0);
    }

    @Override /* 删除动态数组末尾位置的元素 */
    public E removeLast() {
        return remove(this.size-1);
    }

    @Override /* 设置动态数组 index 位置的元素 */
    public void set(int index, E element) {
        rangeCheck(index);
        elementData[index] = element;
    }

    @Override /* 获取动态数组 index 位置的元素 */
    public E get(int index) {
        rangeCheck(index);
        return elementData[index];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("ArrayList : size=%d, capacity=%d, content=[", this.size, this.getCapacity()));
        if (this.size == 0) {
            sb.append(']');
            return sb.toString();
        }
        sb.append(this.elementData[0]);
        for (int i = 1; i < this.size; ++i) {
            sb.append(", " + this.elementData[i]);
        }
        sb.append("]");
        return sb.toString();
    }
    @Override /* 动态数组转普通数组 */
    public E[] toArray() {
        E[] array = (E[]) (new Object[this.size]);
        for (int i = 0; i < this.size; ++i) {
            array[i] = elementData[i];
        }
        return array;
    }
}
